package com.example.design.leetcode.arrayAndString;

//剑指 Offer 57 - II. 和为 s 的连续正数序列 - 解决方案

//题目描述
//        输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
//
//        序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
//
//        示例 1：
//        输入：target = 9
//        输出：[[2,3,4],[4,5]]

//        示例 2：
//        输入：target = 15
//        输出：[[1,2,3,4,5],[4,5,6],[7,8]]

//        限制：
//        1 <= target <= 10^5

// 等差数列求和公式:等差数列的和=(首数+尾数)*项数/2;
// 因为滑动窗口的是一个等差数列，有序增长且步长是1，计算滑动窗口的和 = （left + right）* 元素个数/2
// 元素个数 = right -left + 1

import java.util.ArrayList;
import java.util.List;

// 标签：滑动窗口
public class Practice12 {

    public int[][] findContinuousSequence(int target) {
        int left = 1;
        int right = 2;
        List<int[]> res = new ArrayList<>();

        while(left < right) {
            int sum = (left + right) * (right - left + 1) / 2;
            if (sum == target) {
                int[] arr = new int[right - left + 1];
                for(int k =left; k <= right; k++) {
                    arr[k - left] = k;
                }
                res.add(arr);
                left++;
            } else if (sum < target) {
                right++;
            } else {
                left++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    public int[][] findContinuousSequence2(int target) {
        int left = 1;
        int right = 2;

        List<int[]> res = new ArrayList<>();

        while(left < right) {
            int sum = (right + left) * (right - left + 1) / 2;
            if (sum == target) {
                int[] arr = new int[right - left +1];
                for(int k=left; k<=right; k++) {
                    arr[k-left] =k;
                }
                left++;
                res.add(arr);
            } else if (sum > target) {
                left++;
            } else {
                right++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

}
